package com.mesnac.tree;

public class RBTree {
	// 根节点
	public RBNode root;

	// 空节点
	// public RBNode nil = new RBNode(null,null,null,false);

	/**
	 * 插入节点
	 * 
	 * @param node
	 */
	public void insert(RBNode node) {
		// 判断树是否为空
		if (root == null) {
			root = node;
			root.isRed = false;
			root.left = new RBNode(null, null, null, false);
			root.right = new RBNode(null, null, null, false);
			root.left.parent = root;
			root.right.parent = root;
			return;
		}
		RBNode now = root;
		// 寻找要插入的位置
		while (now.val != null) {
			if (now.val > node.val)
				now = now.left;
			else if (now.val < node.val)
				now = now.right;
			else
				return;
		}
		// 这样我们找到了相应的最后的点，将这个点替换成我们的点
		now.val = node.val;
		now.isRed = true;
		now.left = new RBNode(null, null, null, false);
		now.right = new RBNode(null, null, null, false);
		now.left.parent = now;
		now.right.parent = now;
		// 然后进行树的修正
		insertFix(now);
	}

	public void insertFix(RBNode now) {
		// 如果是根节点，上面应经修正过了，不处理
		System.out.println("现在处理" + now.val);
		if (now == root) {
			if (now.isRed) {
				now.isRed = false;
			}
			return;
		}
		// 如果插入节点的父节点是黑，不处理
		if (!now.parent.isRed) {
			return;
		}
		// 插入的节点父节点红
		if (now.parent.isRed) {
			// 判断父节点是左还是右
			// 父节点是祖父左子
			if (now.parent.parent.left.val == now.parent.val) {
				// 叔叔是红色
				if (now.parent.parent.right.isRed) {
					now.parent.isRed = false;
					now.parent.parent.right.isRed = false;
					now.parent.parent.isRed = true;
					// 当前节点变成父节点

					insertFix(now.parent.parent);
				}
				// 叔叔黑色
				else {

					// 当前节点是右子
					if (now.parent.right.val == now.val) {
						now = now.parent;
						// 左旋
						LRC(now);
						insertFix(now);
					}// 当前节点左子
					else {
						now.parent.isRed = false;
						now.parent.parent.isRed = true;
						// 祖父右旋
						// System.out.println("右旋开始了" + now.parent.parent.val);
						LLC(now.parent.parent);
					}
				}
			}
			// 父节点是祖父右子
			else {
				// 叔叔是红色
				if (now.parent.parent.left.isRed) {
					now.parent.isRed = false;
					now.parent.parent.isRed = true;
					now.parent.parent.left.isRed = false;
					System.out.println("变色");
					insertFix(now.parent.parent);

				}
				// 叔叔黑色
				else {
					// 当前节点是左子
					if (now.parent.left.val == now.val) {
						now = now.parent;
						// 左旋
						System.out.println("左旋开始" + now.val);
						RLC(now);
						insertFix(now);
					}// 当前节点左子
					else {
						now.parent.isRed = false;
						now.parent.parent.isRed = true;
						// 祖父右旋
						// System.out.println("右旋开始" + now.val);
						RRC(now.parent.parent);
					}
				}

			}
		}

	}

	// (父节点是祖父节点的左节点,当前节点是父节点右子),传入父节点
	public void LRC(RBNode node) {
		if (node.val == 15) {
			System.out.println("LRC" + node.val);
		}
		RBNode gfather = node.parent;
		gfather.left = node.right;
		node.right = node.right.left;
		gfather.left.left = node;

		gfather.left.parent = gfather;
		node.parent = gfather.left;
		node.right.parent = node;

	}

	// (父节点是祖父节点的右孩子,当前节点是左子),传入父节点
	public void RLC(RBNode node) {
		System.out.println("RLC" + node.val);
		RBNode gfather = node.parent;
		System.out.println("RLC" + gfather.val);
		gfather.right = node.left;
		node.left = node.left.right;
		gfather.right.right = node;

		gfather.right.parent = gfather;
		node.parent = gfather.right;
		node.left.parent = node;
		System.out.println("RLCgather" + gfather.val);
		System.out.println("RLC" + node.parent.val);

	}

	// (父节点是祖父节点的左孩子，当前节点是左子)(变色),传入祖父
	public void LLC(RBNode node) {
		// 左还是右
		// 左
		System.out.println("祖父节点" + node.val);
		if (node == root) {
			this.root = node.left;
			node.left = node.left.right;
			root.right = node;
			root.left.parent = root;
			root.right.parent = root;
			node.left.parent = node;
			return;
		}
		RBNode gfather = node.parent;
		System.out.println("gf" + gfather.val);
		RBNode father = node.left;
		if (gfather.left.val == node.val)
			gfather.left = node.left;
		else
			gfather.right = node.left;
		node.left = node.left.right;
		father.right = node;

		father.parent = gfather;
		node.parent = father;
		node.left.parent = node;
	}

	// 父节点是祖父的右孩子，当前节点是右子(变色),传入祖父
	public void RRC(RBNode node) {
		if (node == root) {
			this.root = node.right;
			node.right = node.right.left;
			root.left = node;

			root.left.parent = node;
			root.right.parent = node;
			node.right.parent = node;
			return;
		}
		System.out.println("RRC" + node.val);
		RBNode gfather = node.parent;
		RBNode father = node.right;
		if (gfather.left.val == node.val)
			gfather.left = node.right;
		else
			gfather.right = node.right;
		node.right = node.right.left;
		father.left = node;

		father.parent = gfather;
		node.parent = father;
		node.right.parent = node;

	}

	public RBNode getNode(RBNode node) {
		RBNode now = root;
		while (now.val != node.val && now.val != null) {
			if (now.val > node.val) {
				now = now.left;
			} else {
				now = now.right;
			}
		}
		return now;
	}

	public void remove(RBNode node) {
		System.out.println("要删掉" + node.val + node.isRed);
		RBNode parent = node.parent;
		if (node != root) {
			if (node.left.val == null) {
				// 判断这个节点是左还是右
				if (parent.left.val == node.val) {
					parent.left = node.right;
					node.right.parent = parent;
				} else {
					parent.right = node.right;
					node.right.parent = parent;
				}

				if (!node.isRed) {
					removeFix(node.right);
				}
			} else if (node.right.val == null && node.left.val != null) {
				if (parent.left.val == node.val) {
					parent.left = node.left;
					node.left.parent = parent;
				} else {
					parent.right = node.left;
					node.left.parent = parent;
				}

				if (!node.isRed)
					removeFix(node.left);
			} else {
				// 左儿子的最大元素
				RBNode now = node.left;
				while (now.val != null) {
					now = now.right;
				}
				now = now.parent;
				node.val = now.val;
				remove(now);
			}

		} else {
			if (node.left.val == null && node.right.val != null) {
				root = node.right;
				return;
			} else if (node.left.val != null && node.right.val == null) {
				root = node.left;
				return;
			} else if (node.left.val == null && node.right.val == null) {
				root = null;
				return;
			} else {
				// 左儿子的最大元素
				RBNode now = node.left;
				while (now.val != null) {
					now = now.right;
				}
				now = now.parent;
				root.val = now.val;
				remove(now);
			}
		}

	}

	public void removeFix(RBNode node) {
		System.out.println("当前" + node.val + node.isRed + "父节点"
				+ (node.parent == null ? null : node.parent.val));
		if (node.isRed) {
			System.out.println("当前节点，红色" + node.val);
			node.isRed = false;
			return;
		}
		if (!node.isRed && node == root) {
			// do nothing
			System.out.println("当前为根节点" + node.val);
			return;
		}
		// 当前节点是黑+黑，且兄弟节点是红色
		RBNode brother;
		if (node.parent.left.val == node.val) {
			brother = node.parent.right;
		} else {
			brother = node.parent.left;
		}
		if (!node.isRed && brother.isRed && !brother.left.isRed
				&& !brother.right.isRed) {
			// 当前节点左
			System.out.println("当前黑+黑，且兄弟红，孩子黑" + node.val);
			if (node.parent.left.val == node.val) {
				node.parent.isRed = true;
				node.parent.right.isRed = false;
				//左旋
				RLC(node.parent.right);
			}
			// 当前节点右
			else {
				node.parent.isRed = true;
				node.parent.left.isRed = false;
				//
				LRC(node.parent.left);
			}
			removeFix(node);
		}
		// 当前节点黑+黑,兄弟节点黑
		if (!node.isRed && !brother.isRed && !brother.left.isRed
				&& !brother.right.isRed) {
			// 当前节点左
			System.out.println("当前黑+黑，且兄弟黑,孩子黑" + node.val);
			if (node.parent.left.val == node.val) {
				node.parent.right.isRed = true;
			}
			// 当前节点右
			else {

				node.parent.left.isRed = true;
			}
			removeFix(node.parent);
		}
		// 当前节点黑+黑,兄弟黑，且兄弟左子红，右子黑
		if (!node.isRed && !brother.isRed && brother.left.isRed
				&& !brother.right.isRed&&node.parent.left.val == node.val) {
			System.out.println("当前节点黑+黑,兄弟黑，且兄弟左子红，右子黑" + node.val);
			
				brother.isRed = true;
				brother.left.isRed = false;
				// 解右旋
				RBNode bfather = brother.parent;
				bfather.right = brother.left;
				brother.left = brother.left.right;
				brother.left.right = brother;

				bfather.right.parent = bfather;
				brother.left.parent = brother;
				brother.parent = bfather.right;

				removeFix(node);
		}
		if(!node.isRed && !brother.isRed && brother.left.isRed
				&& !brother.right.isRed&&node.parent.right.val == node.val){
			brother.isRed = true;
			brother.left.isRed = false;
			// 解右旋
			RBNode bfather = brother.parent;
			bfather.left = brother.left;
			brother.left = brother.left.right;
			brother.left.right = brother;

			bfather.left.parent = bfather;
			brother.left.parent = brother;
			brother.parent = bfather.left;
			removeFix(node);
		}
		// 当前节点黑+黑,兄弟黑，兄弟右子红色，左子颜色任意
		if (!node.isRed && !brother.isRed && brother.right.isRed) {
			System.out.println("当前节点黑+黑,兄弟黑，且兄弟左子任意，右子红" + node.val);
			if (node.parent.left.val == node.val) {

				RBNode parent = node.parent;
				brother.isRed = parent.isRed;
				parent.isRed = false;
				brother.right.isRed = false;
				// 左旋
				// 祖父节点
				if (parent.parent != null) {
					// 左
					if (parent.parent.left.val == parent.val) {
						// 左旋
						parent.parent.left = brother;
						parent.right = brother.left;
						brother.left = parent;

						brother.parent = parent.parent;
						parent.parent = brother;
						parent.right.parent = parent;
						System.out.println("左旋一次" + parent.val);

					} else {
						parent.parent.right = brother;
						parent.right = brother.left;
						brother.left = parent;

						brother.parent = parent.parent;
						parent.parent = brother;
						parent.right.parent = parent;
					}
				} else {
					// parent本身是根节点
					root = brother;
					parent.right = brother.left;
					root.left = parent;

					root.left.parent = root;
					parent.right.parent = parent;
				}

			} else {

				RBNode parent = node.parent;
				brother.isRed = parent.isRed;
				parent.isRed = false;
				brother.right.isRed = false;
				// 左旋
				// 祖父
				if (parent.parent != null) {
					// 左
					if (parent.parent.left.val == parent.val) {
						// 左旋
						parent.parent.left = brother;
						parent.right = brother.left;
						brother.left = parent;

						brother.parent = parent.parent;
						parent.parent = brother;
						parent.right.parent = parent;
					} else {
						parent.parent.right = brother;
						parent.right = brother.left;
						brother.left = parent;

						brother.parent = parent.parent;
						parent.parent = brother;
						parent.right.parent = parent;
					}
				} else {
					// parent本身是根节点
					root = brother;
					parent.right = brother.left;
					root.left = parent;

					root.left.parent = root;
					parent.right.parent = parent;
				}

			}
		}
	}

	// 先序遍历
	public void MLR(RBNode now) {

		System.out.println(now.val);
		if (now.left.val != null)
			MLR(now.left);
		if (now.right.val != null)
			MLR(now.right);
	}

	// 中序遍历
	public void LMR(RBNode now) {
		if (now.left.val != null)
			LMR(now.left);
		System.out.println(now.val);
		if (now.right.val != null)
			LMR(now.right);
	}

	// 后序遍历
	public void LRM(RBNode now) {
		if (now.left != null)
			LRM(now.left);
		if (now.right != null)
			LRM(now.right);
		if (now.val != null)
			System.out.println(now.val);
	}

	public static void main(String args[]) {

		RBTree a = new RBTree();
		RBNode node = new RBNode(null, null, 12, true);
		a.insert(node);
		node = new RBNode(null, null, 1, true);
		a.insert(node);
		node = new RBNode(null, null, 9, true);
		a.insert(node);

		node = new RBNode(null, null, 2, true);
		a.insert(node);

		node = new RBNode(null, null, 0, true);
		a.insert(node);

		node = new RBNode(null, null, 11, true);
		a.insert(node);
		node = new RBNode(null, null, 7, true);
		a.insert(node);

		node = new RBNode(null, null, 19, true);
		a.insert(node);
		node = new RBNode(null, null, 4, true);
		a.insert(node);

		node = new RBNode(null, null, 15, true);
		a.insert(node);
		//
		node = new RBNode(null, null, 18, true);
		a.insert(node);
		// System.out.println("=="+a.root.right.right.right.val);

		node = new RBNode(null, null, 5, true);
		a.insert(node);
		node = new RBNode(null, null, 14, true);
		a.insert(node);

		node = new RBNode(null, null, 13, true);
		a.insert(node);

		node = new RBNode(null, null, 10, true);
		a.insert(node);

		node = new RBNode(null, null, 16, true);
		a.insert(node);

		node = new RBNode(null, null, 6, true);
		a.insert(node);
		node = new RBNode(null, null, 3, true);
		a.insert(node);
		node = new RBNode(null, null, 8, true);
		a.insert(node);
		node = new RBNode(null, null, 17, true);
		a.insert(node);

		node = new RBNode(null, null, 12, true);
		node = a.getNode(node);
		a.remove(node);

		node = new RBNode(null, null, 1, true);
		node = a.getNode(node);
		a.remove(node);

		node = new RBNode(null, null, 9, true);
		node = a.getNode(node);
		a.remove(node);

		node = new RBNode(null, null, 2, true);
		node = a.getNode(node);
		a.remove(node);

		node = new RBNode(null, null, 0, true);
		node = a.getNode(node);
		a.remove(node);

		

		node = new RBNode(null, null, 11, true);
		node = a.getNode(node);
		a.remove(node);
		
		node = new RBNode(null, null, 7, true);
		node = a.getNode(node);
		a.remove(node);
		
		node = new RBNode(null, null, 19, true);
		node = a.getNode(node);
		a.remove(node);
		System.out.println("===begin");
		a.LMR(a.root);
		/*
		node = new RBNode(null, null, 4, true);
		node = a.getNode(node);
		a.remove(node);

		node = new RBNode(null, null, 15, true);
		node = a.getNode(node);
		a.remove(node); 
		node = new RBNode(null, null, 18, true); 
		node = a.getNode(node);
		a.remove(node);
		// System.out.println("=="+a.root.right.right.right.val);

		node = new RBNode(null, null, 5, true);
		node = a.getNode(node);
		a.remove(node);

		node = new RBNode(null, null, 14, true);
		node = a.getNode(node);
		a.remove(node);

		node = new RBNode(null, null, 13, true);
		node = a.getNode(node);
		a.remove(node);

		node = new RBNode(null, null, 10, true);
		node = a.getNode(node);
		a.remove(node);

		node = new RBNode(null, null, 16, true);
		node = a.getNode(node);
		a.remove(node);

		node = new RBNode(null, null, 6, true);
		node = a.getNode(node);
		a.remove(node);
		
		node = new RBNode(null, null, 3, true);
		node = a.getNode(node);
		a.remove(node);
		
		
		node = new RBNode(null, null, 8, true);
		node = a.getNode(node);
		a.remove(node);
		
		node = new RBNode(null, null, 17, true);
		node = a.getNode(node);
		a.remove(node);
		*/

	}

}
